package practice.Day5;

/**
 * @Author quan
 * @Description 连续最大和:通过80%
 * @Date 2023/5/12 10:09
 */
public class Num2_MaxSum {
    /**
     * 思路总结：关键字有两个：连续的子序列，求和。所以这是一个求sum+=的问题。
     * 1、获取输入数据：写入数组中
     * 2、初始化最大值为数组中的第一个元素
     * 3、双层遍历：外层遍历表示连续子序列的开始位置。内层遍历表示连续子序列的结束位置
     * 4、在内层循环中将每次获取到的子序列的和与最大值相比，如果大于当前最大值，就更新最大值
     * 5、外层 遍历中 不断的获取新的子序列的开始位置，直到数组遍历结束。
     * @param args
     */
    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[] arr = new int[n];
//        int[] arr = {-1,-2,0,-4,-5};
        int[] arr = {1,-2,3,0,4};
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = sc.nextInt();
//        }
        //找到数组中的最大值作为maxSum 的初始值

        int maxSum = arr[0];
        //遍历的次数
        for (int i = 0; i < arr.length-1; i++) {
            int sum = arr[i];
            //求的是每一层的和
            for (int j = i; j < arr.length-1; j++) {
                sum += arr[j+1];
                if(sum > maxSum){
                    maxSum = sum;
                }
            }
        }
        System.out.println(maxSum);
    }
}
